1. Field of the Invention
The invention relates to scan techniques for sequential circuits. In particular, this invention relates to new partial scan techniques using peripheral partitioning and tree decomposition. The invention is embodied in a system to perform partial scan using peripheral partitioning and tree decomposition, in a method for partial scan using peripheral partitioning, in a method for partial scan using tree decomposition, and in a computer program product for enabling a computer to operate according to the method.
2. Related Work
Complexity of testing sequential circuits is well known in the prior art. Two fundamentally different approaches have been pursued in the prior art to reduce the complexity of testing sequential circuits: (1) a synthesis approach, where practitioners synthesize circuits that are easy to test, and/or (2) a design for testability approach, where post-synthesis modification techniques are employed to facilitate easy testing of the circuit.
The synthesis approach requires prohibitive computational resources. Also, when a hierarchical design methodology is used, integrating testability requirements involving different blocks or modules is difficult
Design for testability techniques such as scan have been used widely for achieving high test coverage for sequential circuits. In scan techniques, memory elements (including flip-flops) in a circuit are chained into a shift register. A full scan involves the chaining of all the shift registers in the circuit to be tested. Scan provides for direct controllability and observability of all memory elements during the test mode. However, area and performance penalties of full scan design are unacceptable for many sequential circuit designs.
Partial scan techniques involve selecting only a subset of memory elements. This reduces area and performance penalties involved in a full scan.
Several approaches for selecting memory elements for partial scan have been suggested in the prior art. Testability analysis based approach is one of the approaches that is known in the prior art. See E. Trischler, xe2x80x9cIncomplete Scan Path with an Automatic Test Generation Methodology,xe2x80x9d in Proceedings of the international Test Conference, pp. 153-162, 1980; M. Abramovici, J. J. Kulikowski, and R. K. Roy, xe2x80x9cThe Best Flip-Flops to Scan,xe2x80x9d in Proceedings of the International Test Conference, pp. 166-173, 1991; K. S. Kim and C. R. Kime, xe2x80x9cPartial Scan by Use of Empirical Testability,xe2x80x9d in Proceedings of the International Conference on Computer-Aided Design, pp. 314-317, November 1990; P. S. Parikh and M. Abramovici, xe2x80x9cA Cost Based Approach to Partial Scan,xe2x80x9d in Proceedings of the 30th ACM/IEEE Design Automation Conference, pp. 255-259, June 1993 and D. Xiang and J. H. Patel, xe2x80x9cA Global Algorithm for the Partial Scan Design Problem using Circuit State Information,xe2x80x9d in Proceedings of the International Test Conference, pp. 548-557, October 1996.
Another method suggested in the prior art is a test generation based approach. See V. D. Agrawal, K. T. Cheng, D. D. Johnson, and T. Lin, xe2x80x9cDesigning Circuits with Partial Scan,xe2x80x9d IEEE Design and Test of Computers, vol. 5, pp. 8-15, April 1988; H.-K. T. Ma, S. Devadas, A. R. Newton, and A. Sangiovanni-Vincentelli, xe2x80x9cAn Incomplete Scan Design Approach to Test Generation for Sequential Machines,xe2x80x9d in Proceedings of the International Test Conference, pp. 730-734, 1988; V. Chickermane and J. H. Patel, xe2x80x9cA Fault Oriented Partial Scan Design Approach,xe2x80x9d in Proceedings of the International Conference on Computer-Aided Design, pp. 400-403, November 1991; I. Park, D. S. Ha, and G. Sim, xe2x80x9cA New Method for Partial Scan Design based on Propagation and Justification Requirements of Faults,xe2x80x9d in Proceedings of the International Test Conference, pp. 413-422, October 1995; and V. Boppana and W. K. Fuchs, xe2x80x9cPartial Scan Design based on State Transition Modeling,xe2x80x9d in Proceedings of the International Test Conference, pp. 538-547, October 1996.
Functional or state machine analysis based approaches have also been used in the prior art. See V. Boppana and W. K. Fuchs, xe2x80x9cPartial Scan Design based on State Transition Modeling,xe2x80x9d in Proceedings of the International Test Conference, pp. 538-547, October 1996; C.-C. Lin, M. T.-C. Lee, M. Marek-Sadowska, and K.-C. Chen, xe2x80x9cCost Free Scan: A Low Overhead Scan Path Design Methodology,xe2x80x9d in Proc. of the International Conference on Computer-Aided Design, November 1995; C. C. Lin, M. Marek-Sadowska, K. T. Cheng, and M. T. C. Lee, xe2x80x9cTest Point Insertion: Scan Paths through Combinational Logic,xe2x80x9d in Proceedings of the 32nd ACM/IEEE Design Automation Conference, pp. 268-273, June 1995; D. Chang, M. T. C. Lee, M. Marek-Sadowska, T. Aikyo, and K. T. Cheng, xe2x80x9cA Test Synthesis Approach to Reducing BALLAST DFT Overhead,xe2x80x9d in Proceedings of the 34th ACM/IEEE Design Automation Conference, pp. 466-471, June 1997.
Several practitioners have used a structural analysis based approach. See R. Gupta, R. Gupta, and M. A. Breuer, xe2x80x9cThe BALLAST Methodology for Structured Partial Scan Design,xe2x80x9d IEEE Transactions on Computers, vol. C-39, pp. 538-544, April 1990; K. T. Cheng and V. D. Agrawal, xe2x80x9cA Partial Scan Method for Sequential Circuits with Feedback,xe2x80x9d IEEE Transactions on Computers, vol. 39, pp. 544-548, April 1990; D. Lee and S. Reddy, xe2x80x9cOn Determining Scan Flip-Flops in Partial-Scan Designs,xe2x80x9d in Proceedings of the International Conference on Computer-Aided Design, pp. 322-325, November 1990; A. Kunzmann and H. J. Wunderlich, xe2x80x9cAn Analytical Approach to the Partial Scan Problem,xe2x80x9d Journal of Electronic Testing: Theory and Applications, vol. 1, pp. 163-174, 1990; S. Bhawmik, C. J. Lin, K. T. Cheng, and V. D. Agrawal, xe2x80x9cPascant: A Partial Scan and Test Generation System,xe2x80x9d in Custom Integrated Circuits Conference, pp. 17.3.1-17.3.4, 1991; S. E. Tai and D. Bhattacharya, xe2x80x9cA Three Stage Partial Scan Design Method using the Sequential Circuit Flow Graph,xe2x80x9d in Proceedings of the 7th International Conference on VLSI Design, pp. 101-106, January 1994; S. T. Chakradhar, A. Balakrishnan, and V. D. Agrawal, xe2x80x9cAn Exact Algorithm for Selecting Partial Scan Flip-Flops,xe2x80x9d in Proc. of the 31st ACM/IEEE Design Automation Conf., pp. 81-86, June 1994; A. Balakrishnan and S. T. Chakradhar, xe2x80x9cSequential Circuits with Combinational Test Generation Complexity,xe2x80x9d in 9th International Conference on VLSI Design, January 1996; and T. Ono, xe2x80x9cSelecting Partial Scan Flip-flops for Circuit Partitioning,xe2x80x9d in Proceedings of the International Conference on Computer-Aided Design, pp. 646-650, November 1994.
The testability analysis based methods use cost metrics during scan selection. The ability of testability based approaches to tightly correlate with sequential test generation effort required for large designs is not clearly established. Further, one often has to rely on the test generator to refine the measures and/or to gain confidence on the scan selection based on these testability measures. Some of the more sophisticated testability measures require large computational resources.
Test generation based approaches select scan memory elements based on identification of hard-to-detect faults. This approach is tightly coupled with the test generation tool and does not offer the designer any flexibility to determine scan flip-flops a priori. Further, scan selection strongly depends on the order of faults chosen by the test generation.
Often, one may have to perform multiple test generation runs to obtain good scan selection. This approach further constraints the already computationally intensive test generation process. Recent work by V. Boppana and W. K. Fuchs incorporates state machine analysis within the test generation based approach to select partial scan flip-flops. The applicability of such approaches to large designs have not been established.
Another recent functional approach showed that functional or cost-free scan paths can be established for any scan selection. See C.-C. Lin et al., xe2x80x9cCost Free Scan: A Low Overhead Scan Path Design Methodology,xe2x80x9d in Proc. of the International Conference on Computer-Aided Design, November 1995. This method involves computation of ordered binary decision diagrams (OBDD""s). Therefore, it may prove to be computationally expensive for large designs.
Other recent efforts have shown the use of test points to establish functional scan paths. See C. C. Lin, M. Marek-Sadowska, K. T. Cheng, and M. T. C. Lee, xe2x80x9cTest Point Insertion: Scan Paths through Combinational Logic,xe2x80x9d in Proceedings of the 32nd ACM/IEEE Design Automation Conference, pp. 268-273, June 1995 and D. Chang, M. T. C. Lee, M. Marek-Sadowska, T. Aikyo, and K. T. Cheng, xe2x80x9cA Test Synthesis Approach to Reducing BALLAST DFT Overhead,xe2x80x9d in Proceedings of the 34th ACM/IEEE Design Automation Conference, pp. 466-471, June 1997. These techniques can be used to complement any scan selection approach, including the present invention, to provide an effective way to implement/synthesize scan chains.
Structural partial scan methods analyze the structure of the flip-flop dependency graph and base their scan selection on structural properties of this graph. Most of the structural methods have centered around breaking feedback loops, a technique first introduced by Cheng et al. See Cheng and V. D. Agrawal, xe2x80x9cA Partial Scan Method for Sequential Circuits with Feedback,xe2x80x9d IEEE Transactions on Computers, vol. 39, pp. 544-548, April 1990. This approach called self-loop acyclic all feedback loops except self-loops are broken. A self-loop here refers to a situation where the output of a flip-flop, after passing through combinational logic, feeds back into the same flip-flop. This approach results in low area overhead, however, it is not effective for test generation.
At the other extreme one can break all feedback loops including self-loops. This approach called pipeline, results in a scan circuit with almost combinational ATPG complexity. See H. B. Min and W. A. Rogers, xe2x80x9cA Test Methodology for Finite State Machines using Partial Scan Design,xe2x80x9d Journal of Electronic Testing: Theory and Applications, vol. 3, pp. 127-137, May 1992. However, this approach can result in high area overhead because most of the flip-flops in a typical design have self-loops. An extension of the pipeline approach advocates limiting the sequential depth of the design during the test mode.
Several partial scan techniques have been proposed recently but they either lack the ability to provide adequate test coverage for modest to large designs or they do not yield significant reduction in area/performance penalties as compared to full scan design. For example, consider the two analogous approaches for partial scan: one selecting flip-flops to break all feedback cycles except self-loops (self-loop acyclic) and the other selecting flip-flops to break all feedback cycles including self-loops (pipeline). FIG. 13 depicts a table showing area overhead and test generation results for the larger benchmark circuits. The data shows that self-loop acyclic technique entails low area overhead but the scanned circuits are hard to test. Pipeline method produces circuits that are easy to test but this method entails high area overhead.
It is an objective of this invention to solve the problems associated with partial scan techniques.
In the current invention a novel structural decomposition approach for selecting partial scan memory elements that can result in circuits with very high test coverage while entailing low area/performance penalties is disclosed. The distinguishing features of the approach used in the current invention are (a) it drastically reduces the test generation effort (b) it will scale well for large designs without compromising on test coverage and (c) it is easy to implement like fill-scan design or any structural approach.
Specifically an objective of this invention is to provide a method of performing partial scan of a sequential circuit using peripheral partitioning.
It is another objective of this invention to provide a method for performing partial scan of a sequential circuit using tree decomposition.
Yet another objective of this invention is to provide a method for partitioning a sequential circuit into peripheral partitions.
Yet another objective of this invention is to provide a method to solve the cycle cut-set problem, associated with peripheral partitioning.
Yet another objective of this invention is to provide a method for tree decomposition of an undirected graph, representing a sequential circuit, into trees.
Yet another objective of this invention is to provide a system that uses peripheral partitioning method and the tree decomposition method of the current invention to form a partial scanned circuit.
Yet another objective of this invention is to provide a program product that enables a computer to perform the peripheral partitioning method and the tree decomposition method of the current invention to form partial scanned circuit.
To achieve the objectives of the invention, it is provided a partial scan system for sequential circuits comprising an input unit, a peripheral partitioning unit, a tree decomposition unit, a circuit redesign unit and an output unit.
Another embodiment of the present invention is a system and method of partial scan for a sequential circuit using peripheral partitioning. This invention also includes a system and method of partial scan for a sequential circuit using tree decomposition.
Another embodiment of this invention is a system and method of peripheral partitioning a sequential circuit to form a plurality of partitions, wherein each of said plurality of partitions comprise a group of memory elements, each memory element in said group of memory element do not form a combination path with memory elements not belonging to said group of memory elements.
Another embodiment of this invention is a method of peripheral partitioning a sequential circuit comprising: drawing an S-graph of the sequential circuit; remodeling the S-graph into a new undirected graph; eliminating cycles in the new undirected graph by selecting a minimal set of vertices.
Another embodiment of this invention is a method of selecting a minimal set of vertices to break all cycles comprising computing bi-connected components to form a plurality of bi-connected components; adding one vertex from each of said plurality of bi-connected components to a cycle cut-set; removing said one vertex from each of said plurality of bi-connected components; and repeating the steps until there are no more bi-connected components.
Another embodiment of the current invention is a method of tree decomposition of an S-graph with a plurality of vertices, each of said plurality of vertices having an out-degree, a plurality of in-degree vertices and a cost, said method comprising: computing out-degree for each vertex; initializing said cost of said each vertex to zero using the formula: cost (v)=0, wherein v is said each vertex, wherein cost(v) is cost of said each vector v; updating cost of said each vertex using the formula: cost(v)=out-degree(v)xe2x88x921, if out-degree(v) is greater than 1, wherein out-degree(v) is said out-degree of said each vertex v; updating cost of said each vertex using the formula: cost(v)=cost(v)+one, if out-degree(w) greater than 1, wherein w is each said in-degree vertex of v, wherein out-degree(w) is said out-degree of w; repeating the previous step for each in-degree vertex of v; repeating cost calculations for each vertex in the graph; removing a vertex with the maximum cost and adding to said cut-set list; repeating the whole cost computation process until updated cost for each vertex not removed is less than or equal to 0; and returning said cut-set list.
Another embodiment of this invention is a computer program product comprising, computer readable instructions, and a computer readable medium bearing said computer readable instructions; said instructions being adaptable to enable a computer to operate according to the steps of: receiving a sequential circuit from the user; tree decompositioning the circuit for a partial scan; returning the partial scan circuit to the user.
Another embodiment of this invention is a computer program product comprising, computer readable instructions and a computer medium bearing said computer readable instructions; said instructions being adaptable to enable a computer to operate according to the steps of: receiving a sequential circuit from the user; peripheral partitioning the circuit to form a partial scanned circuit; checking if tree decompositioning can be performed on this partial scanned circuit; tree decompositioning the circuit if tree decompositioning can be performed on the circuit to form a refined partial scanned circuit; returning the refined partial scanned circuit to the user.